//KMP算法
//knuth_morris_pratt.cpp

//在较长的文本中查找一个字符串

//为了方便与代码中的数组下标统一，本文中字符串的下标都从0开始
//1)考虑一个文本"BBC ABCDAB ABCDABCDABDE"，在其中查找一个字符串"ABCDABD"
//i)从文本的起始处B开始匹配：
//BBC ABCDAB ABCDABCDABDE
//ABCDABD
//ii)第0个字符不同，将字符串移动到下一个字符B也不同，一直到第4个字符A(算空格)：
//BBC ABCDAB ABCDABCDABDE
//    ABCDABD
//字符串第字6符D不匹配，从0到5字符匹配，按照原始的方法应该继续匹配文本中的第5字符B
//但在这里使用前缀函数(先不考虑如何构造)，本问题中的字符串的前缀函数prefix为：
//ABCDABD
//0000120
//当字符串移动到文本第4个字符A时
//下一次移动的距离 = 字符串中最后一个匹配的字符下标 - 该字符的前缀函数 + 1
//注意该公式中的下标都是按照数组下标计算的，从0开始
//这时字符串中最后一个匹配的是第5个字符B，因此下一次移动的距离 = 5 - 2 + 1 = 4
//其中5为最后一个匹配的字符B的下标，2为该字符前缀函数值
//iii)移动4个位置后字符串到达文本第8个字符A：
//BBC ABCDAB ABCDABCDABDE
//        ABCDABD
//字符串中第1个字符B是最后匹配的，应用前缀函数可知移动距离 = 1 - 0 + 1 = 2
//iv)移动2个位置后到达文本第10个字符' '：
//BBC ABCDAB ABCDABCDABDE
//          ABCDABD
//v)字符串第0个字符不匹配
//当字符串中没有匹配到的字符时，不使用前缀函数，直接后移一位
//BBC ABCDAB ABCDABCDABDE
//           ABCDABD
//vi)字符串中最后一个匹配的字符是第5个字符B
//移动距离 = 5 - 2 + 1 = 4，向后移动4个位置：
//BBC ABCDAB ABCDABCDABDE
//               ABCDABD
//字符串与文本第16个字符A匹配，算法结束
//
//2)前缀与后缀
//对于一个字符串x，如果有x = yz，其中y和z也是字符串(可以是空串)
//则称字符串y是x的前缀，且|y|<=|x|
//类似的字符串z是x的后缀，且|z|<=|x|
//比如字符串x = "abcd"，它的前缀字符串有""(空串)，"a"，"ab"，"abc"，"abcd"
//后缀字符串有""(空串)，"d"，"cd"，"bcd"，"abcd"
//
//2)有限自动机
//虽然上述算法中的例子非常好懂，但实际上构造前缀函数是一个非常抽象的数学过程
//有限自动机是编译原理中的概念，应用在字符串匹配问题中即为字符串匹配自动机
//通过使用后缀函数和变迁函数的技术可以得到字符串的所有信息
//从而使自动机可以做到扫描一遍文本就匹配到所有字符串
//
//自动机的原理比较抽象难懂，本文也不再详述
//有兴趣的读者可以参考算法导论第32章字符串匹配32.3利用有限自动机进行字符串匹配
//
//3)前缀函数
//考虑文本text为"bacbababaabcbab"，字符串str为"ababaca"：
//b a c b a b a b a a b c b a b
//        a b a b a c a
//前缀函数的数学解释也比较难懂，有兴趣的读者可以参考算法导论中相关的概念与定理
//最简单的解释就是对于字符串str设置数组prefix
//prefix[i]指代str中前i个字符的前缀函数值，即上文的前缀函数
//
//我希望着重指出的是：prefix[i]数组中的i代表的意义是，字符串中前“i”个字符
//对应下标是从0到i-1的子串，不匹配的字符下标是i
//重点提出来，是因为大多数资料中将字符串从1开始计算，而编程时数组则从0开始
//在实际编程中非常容易搞混，希望读者可以注意这个细节
//在解释前缀函数这一部分中，字符串的说明都是说“前i个字符”，而不是指下标
//
//这时字符串str已经匹配前5个字符，q = 5
//只考虑已经匹配的字符所组成的子串"ababa"，它的前缀函数prefix[5]的值为：
//
//算法导论中的原文是“子串(指字符串str的子串"ababa")的真后缀P的最长前缀的长度”
//这句难以理解的话就是前缀函数的核心
//以及公式prefix[q] = “max{k: k < q 且 Pk 后缀于 Pq}”
//其中Pk和Pq是匹配字符串"ababaca"的前k和前q个字符组成的字符串，Pk是Pq的后缀
//当q = 5时，Pq = "ababa"
//
//参考网络上一些文档的描述，可以得到的更容易理解的解释是：
//在本文的字符串str的前5个字符的子串"ababa"中
//它的真后缀有：""，"a"，"ba"，"aba"，"baba"
//它的前缀有：""，"a"，"ab"，"aba"，"abab"，"ababa"
//在这前缀和真后缀的两个集合中，相同且长度最长的那个字符串就是"aba"，它的长度3就是解
//
//算法导论原书中有一个关于字符串"ababababca"的前缀函数的例子：
//a b a b a b a b c a
//0 0 1 2 3 4 5 6 0 1
//我们来用上述的解释来进行验证
//由于算法导论中的字符串是从1开始计数，与数组下标不同，因此q从1开始
//字符串从1开始还是从0开始一个非常容易让人搞混的问题
//
//q = 1时子串为"a"，真后缀：{""}，前缀：{"","a"}
//相同的最长的字符串为""，长度0
//q = 2时子串为"ab"，真后缀：{"","b"}，前缀：{"","a","ab"}
//相同的最长的字符串为""，长度0
//q = 3时子串为"aba"，真后缀：{"","a","ba"}，前缀：{"","a","ab","aba"}
//相同的最长的字符串为"a"，长度1
//q = 4时子串为"abab"，真后缀：{"","b","ab","bab"}
//前缀：{"","a","ab","aba","abab"}，字符串为"ab"，长度2
//q = 5时子串为"ababa"，真后缀：{"","a","ba","aba","baba"}
//前缀：{"","a","ab","aba","abab","ababa"}，字符串为"aba"，长度3
//...
//q = 9时子串为"ababababc"
//真后缀：{"","c","bc","abc","babc","ababc","bababc","abababc","babababc"}
//前缀：{"","a","ab","aba","abab","ababa","ababab","abababa","abababab","ababababc"}
//字符串为""，长度0
//q = 10时子串为"ababababca"
//真后缀：{"","a","ca","bca",...,"babababca"}
//前缀：{"","a","ab","aba",...,"ababababc","ababababca"}
//字符串为"a"，长度1
//
//由此可以验证前缀函数prefix[q]是匹配字符串中由前q个字符，即从0到q-1字符组成的子串中
//前缀和真后缀两个字符串集合中相同的，且长度最长的字符串的长度
//
//计算匹配字符串str的每个字符的prefix即可得到本文开始使用的前缀函数数组
//
//4)前缀函数与移动位置
//在文本text的某个位移s处，文本匹配了字符串str的前q个字符
//即字符串str中从0到q-1字符匹配，第q字符不匹配(这里q是字符串下标)
//根据本文一开始的公式：
//下一次移动的距离 = 字符串中最后一个匹配的字符下标 - 该字符下标的前缀函数 + 1
//则有移动位移 = q-1 - prefix[q-1] + 1，当q = 0时不使用这个公式，直接移动1位
//可以化为：
//移动位移 = q - prefix[q-1]
//注意这里的q是字符串数组中不匹配的字符下标
//
//我希望着重指出的是：prefix[i]数组中的i代表的意义是，字符串中前“i”个字符
//即对应下标是从0到i-1的子串，不匹配的字符下标是i
//重点提出来，是因为大多数资料中将字符串从1开始计算，而编程时数组则从0开始
//在实际编程中非常容易搞混，希望读者可以注意这个细节
//
//本文忠实的实现了算法导论中关于KMP算法的伪语言描述
//
//本文引用了“字符串匹配的KMP算法”，作者“阮一峰”
//“KMP算法详解——适合初学KMP算法的朋友”，作者“Bill_Hoo”

#include "general_head.h"
void compute_prefix(string s, int *p);

void knuth_morris_pratt(string s, string t, vector<int>& pos)
{//字符串s在文本t中进行匹配
 //返回字符串在文本中匹配到的子串的数量和位置，存储于数组pos中
 	pos.clear();
	int pref[MAX];
	//计算字符串s的前缀函数pref
	compute_prefix(s, pref);
	int i(0);
	while(i < (int)t.length()){
		int q(0);
		while(q < (int)s.length() && s[q] == t[i + q])
			++ q;
		if(q == (int)s.length())
			pos.push_back(i);
		if(q == 0)
			++ i;
		else
			//移动位移i = q - prefix[q - 1]
			//这里的q是字符串不匹配的字符下标
			i += q - pref[q - 1];
	}
}
void compute_prefix(string s, int *pref)
{
	pref[0] = 0;
	int k(0);
	for(int i = 1; i < (int)s.length(); ++ i){
		//s中从0到i这个字符串s[0...i]
		//的前缀和真后缀中相同且最长的子串的长度
		while(k > 0 && s[k] != s[i])
			k = pref[k];
		if(s[k] == s[i])
			++ k;
		pref[i] = k;
	}
}
